package org.example.myleet.priorityqueue;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.Parser;

import java.util.*;

public class PriorityQueueSolution {

    //面试题 17.09. 第 k 个数
    public int getKthMagicNumber(int k) {
        Set<Long> existNumber = new HashSet<>();
        PriorityQueue<Long> priorityQueue = new PriorityQueue<>(Comparator.naturalOrder());
        priorityQueue.offer(1L);
        existNumber.add(1L);
        long res = 1L;
        while (k > 0) {
            long top = priorityQueue.poll();
            res = top;
            long nextNumber = top * 3L;
            if (existNumber.add(nextNumber)) {
                priorityQueue.offer(nextNumber);
            }
            nextNumber = top * 5L;
            if (existNumber.add(nextNumber)) {
                priorityQueue.offer(nextNumber);
            }
            nextNumber = top * 7L;
            if (existNumber.add(nextNumber)) {
                priorityQueue.offer(nextNumber);
            }
            --k;
        }
        return (int) res;
    }

    /**
     * 264【优先队列】丑数 II
     * 68 ms
     * 最小堆方法，最小堆每次都优先取出的是最小的丑数，丑数生成的丑数加入到最小堆中
     * 注意两点，1、最小堆要防止重复丑数加入；2、题目最大n为1660，要注意int会溢出，需要用long
     */
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> heap = new PriorityQueue<>();
        heap.offer(1L);
        Set<Long> existUglyNumber = new HashSet<>();
        long kthUglyNumber = heap.poll();
        for (int i = 1; i < n; ++i) {
            long nextUglyNumber = kthUglyNumber * 2;
            if (!existUglyNumber.contains(nextUglyNumber) && nextUglyNumber > 0) {
                existUglyNumber.add(nextUglyNumber);
                heap.offer(nextUglyNumber);
            }
            nextUglyNumber = kthUglyNumber * 3;
            if (!existUglyNumber.contains(nextUglyNumber) && nextUglyNumber > 0) {
                existUglyNumber.add(nextUglyNumber);
                heap.offer(nextUglyNumber);
            }
            nextUglyNumber = kthUglyNumber * 5;
            if (!existUglyNumber.contains(nextUglyNumber) && nextUglyNumber > 0) {
                existUglyNumber.add(nextUglyNumber);
                heap.offer(nextUglyNumber);
            }
            kthUglyNumber = heap.poll();
        }
        heap.clear();
        return (int) kthUglyNumber;
    }

    /**
     * 295【优先队列】数据流的中位数
     */
    static class MedianFinder {

        //小根堆
        private PriorityQueue<Integer> leastHeap;

        //大根堆
        private PriorityQueue<Integer> biggestHeap;

        /** initialize your data structure here. */
        public MedianFinder() {
            //小根堆会将数字维护成类似，堆顶->4、5、6
            leastHeap = new PriorityQueue<>(Comparator.naturalOrder());
            //大根堆会将数字维护成类似，堆顶->3、2、1
            biggestHeap = new PriorityQueue<>(Comparator.reverseOrder());
        }

        public void addNum(int num) {
            if (leastHeap.size() == 0) {
                leastHeap.offer(num);
                return;
            }
            //本方案会优先向对应的堆插入数字，然后再平衡堆
            if (num >= leastHeap.peek()) {
                leastHeap.offer(num);
            } else {
                biggestHeap.offer(num);
            }
            while (leastHeap.size() < biggestHeap.size()) {
                leastHeap.offer(biggestHeap.poll());
            }
            while (leastHeap.size() - biggestHeap.size() > 1) {
                biggestHeap.offer(leastHeap.poll());
            }
        }

        public double findMedian() {
            if (leastHeap.size() == 0) {
                //这个是测试的时候发现的提示，意思是不能在数据为空的时候调用此方法
                throw new RuntimeException("'findMedian' arguments are invalid: There should be at least one element in the data structure to call findMedian()");
            }
            if (leastHeap.size() > biggestHeap.size()) {
                //由于优先向小根堆插入数字，因此如果两个堆的大小不同，说明是奇数，直接返回中位数
                return leastHeap.peek();
            } else {
                //偶数情况，返回中间两个数的均值作为中位数
                return (leastHeap.peek() + biggestHeap.peek()) / 2.0;
            }
        }
    }

    /**
     * 373【优先堆】查找和最小的 K 对数字
     */
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int BASE = 10000;
        int n1 = nums1.length, n2 = nums2.length;
        HashSet<Integer> visited = new HashSet<>();
        PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });
        int hash = getHash373(0, 0, BASE);
        heap.offer(new int[]{0, 0, nums1[0] + nums2[0]});
        visited.add(hash);
        List<List<Integer>> result = new ArrayList<>(k);
        for (int i = 0; i < k; ++i) {
            int[] arr = heap.poll();
            List<Integer> tuple = new ArrayList<>(2);
            tuple.add(nums1[arr[0]]);
            tuple.add(nums2[arr[1]]);
            result.add(tuple);
            int i1 = arr[0] + 1;
            int i2 = arr[1] + 1;
            if (i1 >= n1 && i2 >= n2) {
                break;
            }
            if (i1 >= n1) {
                --i1;
            }
            if (i2 >= n2) {
                --i2;
            }
            hash = getHash373(i1, arr[1], BASE);
            if (!visited.contains(hash)) {
                heap.offer(new int[]{i1, arr[1], nums1[i1] + nums2[arr[1]]});
                visited.add(hash);
            }
            hash = getHash373(arr[0], i2, BASE);
            if (!visited.contains(hash)) {
                heap.offer(new int[]{arr[0], i2, nums1[arr[0]] + nums2[i2]});
                visited.add(hash);
            }
        }
        return result;
    }
    private int getHash373(int n1, int n2, int BASE) {
        return n1 * BASE + n2;
    }

    /**
     * 630【贪心+大根堆】课程表 III
     * 首先需要证明，在比较两门课程哪一门先学习时，先学习deadline更小的后学习deadline更大的课程，此方式一定最优，证明见官方题解
     * 有了这个定理之后，我们将courses按deadline从小到大排列，小的课程先学习一定更优
     * 然后需要证明，排序后，在遇到第i门课程会超出deadline时，从第1～i-1门课程中找出duration比第i门课程大的课程j，和课程i进行替换（抛弃j，使用i）
     * 简单理解就是在课程数不变的情况下，减小总体的duration（totalTime）肯定更优
     */
    public int scheduleCourse(int[][] courses) {
        //先学习deadline更小的后学习deadline更大的课程，此方式一定最优，按deadline升序排序
        List<int[]> validCourses = new ArrayList<>(courses.length);
        for (int[] course : courses) {
            //如果所学课程需时大于限时，抛弃
            if (course[0] > course[1]) continue;
            validCourses.add(course);
        }
        validCourses.sort(Comparator.comparingInt(a -> a[1]));
        //大根堆，堆顶的课程是duration最大的
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int totalTime = 0;
        for (int[] course : validCourses) {
            if (heap.isEmpty() || totalTime + course[0] <= course[1]) {
                //还没选课程，或课程可选的情况下，直接选课
                heap.offer(course);
                totalTime += course[0];
            } else {
                //遇到待选课程超出时间的情况下，如果待选课程的所需时间比目前已选课程中最大所需时间更少，那就优先考虑待选课程
                int[] p = heap.peek();
                if (p[0] >= course[0]) {
                    heap.poll();
                    heap.offer(course);
                    totalTime = totalTime - p[0] + course[0];
                }
            }
        }
        return heap.size();
    }

    /**
     * 1094【排序+小根堆】拼车
     */
    public boolean carPooling(int[][] trips, int capacity) {
        Arrays.sort(trips, (a, b) ->{
            return a[1] - b[1];
        });
        int curPC = 0, n = trips.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            return a[1] - b[1];
        });
        for (int i = 0; i < n; ++i) {
            while (!pq.isEmpty() && trips[i][1] >= pq.peek()[1]) {
                curPC -= pq.poll()[0];
            }
            if (capacity < curPC + trips[i][0]) return false;
            curPC += trips[i][0];
            pq.offer(new int[]{trips[i][0], trips[i][2]});
        }
        return true;
    }

    //1499
    public int findMaxValueOfEquation(int[][] points, int k) {
        int answer = Integer.MIN_VALUE;
        int n = points.length;
        int[][] cpPoints = new int[n][3];
        for (int i = 0; i < n; ++i) {
            cpPoints[i][0] = points[i][0];
            cpPoints[i][1] = points[i][1];
            cpPoints[i][2] = points[i][0] + points[i][1];
        }
        int l = 0, r = 1;
        PriorityQueue<int[]> bestPointPq = new PriorityQueue<>((o1, o2) -> o2[2] - o1[2]);
        while (l < n) {
            if (cpPoints[l + 1][0] - cpPoints[l][0] <= k) {
                r = l + 1;
                bestPointPq.offer(cpPoints[r++]);
                break;
            }
            ++l;
        }
        while (l < n) {
            while (r < n && cpPoints[r][0] - cpPoints[l][0] <= k) {
                bestPointPq.offer(cpPoints[r++]);
            }
            while (!bestPointPq.isEmpty() && bestPointPq.peek()[0] <= cpPoints[l][0]) {
                bestPointPq.poll();
            }
            int[] bestPoint = bestPointPq.peek();
            if (null != bestPoint) {
                answer = Math.max(answer, cpPoints[l][1] + bestPoint[1] + bestPoint[0] - cpPoints[l][0]);
            }
            ++l;
            if (r <= l) r = l + 1;
        }
        return answer;
    }

    /**
     * 1631【BFS+小根堆】最小体力消耗路径
     */
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length, n = heights[0].length, em = m - 1, en = n - 1;
        int[][] dirs = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        //每个位置如果作为路径时最大消耗体力值
        int[][] pMaxEffort = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                //初始化为最大值
                pMaxEffort[i][j] = Integer.MAX_VALUE;
            }
        }
        int answer = Integer.MAX_VALUE;
        //利用小根堆保存体力消耗最小的可行路线，0-r，1-c，2-最大消耗体力
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        pq.offer(new int[]{0, 0, 0});
        pMaxEffort[0][0] = 0;
        //模仿BFS的遍历方式
        while (!pq.isEmpty()) {
            int[] p = pq.poll();
            if (p[0] == em && p[1] == en) {
                //走到终点，记录可能的答案
                answer = Math.min(answer, p[2]);
            }
            for (int[] dir : dirs) {
                int r = p[0] + dir[0];
                int c = p[1] + dir[1];
                if (0 <= r && r < m && 0 <= c && c < n) {
                    //计算p点到[r][c]点的体力消耗值curEffort，如果curEffort更小，则此节点可以作为路线，放入小根堆中
                    int curEffort = Math.abs(heights[r][c] - heights[p[0]][p[1]]);
                    if (curEffort < pMaxEffort[r][c]) {
                        pq.offer(new int[]{r, c, Math.max(p[2], curEffort)});
                        pMaxEffort[r][c] = curEffort;
                    }
                }
            }
        }
        return answer;
    }

    /**
     * 1657【堆+位运算】确定两个字符串是否接近
     */
    public boolean closeStrings(String word1, String word2) {
        if (word1.length() != word2.length()) return false;
        int mask1 = 0, mask2 = 0, n = word1.length();
        int[] lc1 = new int[26], lc2 = new int[26];
        PriorityQueue<Integer> pq1 = new PriorityQueue<>(Comparator.naturalOrder()), pq2 = new PriorityQueue<>(Comparator.naturalOrder());
        for (int i = 0; i < n; ++i) {
            char c1 = word1.charAt(i);
            int idx1 = c1 - 'a';
            mask1 |= 1 << idx1;
            lc1[idx1]++;
            char c2 = word2.charAt(i);
            int idx2 = c2 - 'a';
            mask2 |= 1 << idx2;
            lc2[idx2]++;
        }
        //利用位运算mask记录出现过的小写字母，出现过的字母对应的位是1
        if (mask1 != mask2) return false;
        for (int i = 0; i < 26; ++i) {
            //将出现过的字母的统计数放到堆中，最后只要保证弹出的数字一样就可以通过操作2实现变换
            if (lc1[i] > 0) pq1.offer(lc1[i]);
            if (lc2[i] > 0) pq2.offer(lc2[i]);
        }
        while (!pq1.isEmpty()) {
            if (!Objects.equals(pq1.poll(), pq2.poll())) return false;
        }
        return true;
    }

    /**
     * 1705【优先堆】吃苹果的最大数目
     */
    public int eatenApples(int[] apples, int[] days) {
        int answer = 0, n = apples.length, day = 0;
        //int[] -> 0-一份苹果的库存数, 1-一份苹果未腐烂的最远的day（保质期）
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (int i = 0; i < n; ++i) {
            if (apples[i] > 0) {
                //有苹果可以吃，存一份
                pq.offer(new int[]{apples[i], i + days[i] - 1});
            }
            while (!pq.isEmpty()) {
                int[] peek = pq.peek();
                //针对吃完的或超过保质期的苹果扔掉
                if (peek[0] < 1 || peek[1] < i) pq.poll();
                else break;
            }
            int[] apple = pq.peek();
            if (null != apple) {
                //吃一个
                --apple[0];
                ++answer;
            }
            //过一天
            ++day;
        }
        //n天之后，如果还有库存的苹果，继续吃
        while (!pq.isEmpty()) {
            int[] apple = pq.peek();
            if (apple[0] < 1 || apple[1] < day) {
                //针对吃完的或超过保质期的苹果扔掉
                pq.poll();
            } else {
                //吃一个
                --apple[0];
                ++answer;
                //过一天
                ++day;
            }
        }
        return answer;
    }

    //p1792
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<double[]> heap = new PriorityQueue<>(((o1, o2) -> Double.compare(o2[2], o1[2])));
        for (int[] c : classes) {
            double[] cl = new double[3];
            cl[0] = c[0];
            cl[1] = c[1];
            cl[2] = (double) (c[0] + 1) / (c[1] + 1) - (double) c[0] / c[1];
            heap.offer(cl);
        }
        while (extraStudents > 0) {
            double[] c = heap.poll();
            double[] cl = new double[3];
            cl[0] = c[0] + 1;
            cl[1] = c[1] + 1;
            cl[2] = (cl[0] + 1) / (cl[1] + 1) - cl[0] / cl[1];
            heap.offer(cl);
            --extraStudents;
        }
        double totalPassRate = 0.0;
        while (!heap.isEmpty()) {
            double[] c = heap.poll();
            totalPassRate += c[0] / c[1];
        }
        double p = totalPassRate / classes.length;
        return p;
    }

    //p1801
    public int getNumberOfBacklogOrders(int[][] orders) {
        int MOD = 1000000007;
        PriorityQueue<int[]> buyHeap = new PriorityQueue<>((o1, o2) -> o2[0] - o1[0]);
        PriorityQueue<int[]> sellHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));
        for (int i = 0; i < orders.length; ++i) {
            int[] order = orders[i];
            if (order[2] == 0) {
                if (sellHeap.isEmpty() || sellHeap.peek()[0] > order[0]) {
                    //无法交易，积压
                    buyHeap.offer(order);
                } else {
                    int[] sell = sellHeap.poll();
                    if (order[1] < sell[1]) {
                        //被卖单吃掉整个订单，还剩余卖单请求
                        sellHeap.offer(new int[]{sell[0], sell[1] - order[1], 1});
                    } else if (order[1] > sell[1]) {
                        //订单未完全消化，重复消化此订单
                        order[1] -= sell[1];
                        --i;
                    }
                }
            } else {
                if (buyHeap.isEmpty() || buyHeap.peek()[0] < order[0]) {
                    //无法交易，积压
                    sellHeap.offer(order);
                } else {
                    int[] buy = buyHeap.poll();
                    if (order[1] < buy[1]) {
                        //被买单吃掉整个订单，还剩余买单请求
                        buyHeap.offer(new int[]{buy[0], buy[1] - order[1], 1});
                    } else if (order[1] > buy[1]) {
                        //订单未完全消化，重复消化此订单
                        order[1] -= buy[1];
                        --i;
                    }
                }
            }
        }
        //统计积压的订单数目
        int block = 0;
        while (!sellHeap.isEmpty()) {
            block += sellHeap.poll()[1];
            block %= MOD;
        }
        while (!buyHeap.isEmpty()) {
            block += buyHeap.poll()[1];
            block %= MOD;
        }
        return block;
    }

    /**
     * 2034【优先队列+哈希表】股票价格波动
     */
    class StockPrice2034 {
        class Bid {
            int time;
            int price;
            //标记这个价格还有没有用
            boolean enable;

            public Bid(int time, int price) {
                this.time = time;
                this.price = price;
                this.enable = true;
            }
        }

        //两个优先队列，一个维护最小的股票价格，一个维护最大的股票价格
        private PriorityQueue<Bid> maxHeap;
        private PriorityQueue<Bid> minHeap;
        private Map<Integer, Bid> map;
        //当前时间戳，用于判断是不是最新的价格
        private int currentTime;
        private int cur;

        public StockPrice2034() {
            maxHeap = new PriorityQueue<>(new Comparator<Bid>() {
                @Override
                public int compare(Bid o1, Bid o2) {
                    return o2.price - o1.price;
                }
            });
            minHeap = new PriorityQueue<>(new Comparator<Bid>() {
                @Override
                public int compare(Bid o1, Bid o2) {
                    return o1.price - o2.price;
                }
            });
            map = new HashMap<>();
            currentTime = 0;
        }

        public void update(int timestamp, int price) {
            Bid existBid;
            if ((existBid = map.get(timestamp)) != null) {
                //如果已经存在之前的报价，则将报价置为无效
                existBid.enable = false;
            }
            //如果时间戳是最新的，更新最新报价
            if (timestamp >= currentTime) {
                cur = price;
                currentTime = timestamp;
            }
            //保存对应时间戳的报价，放入优先队列中维护最高最低价
            Bid bid = new Bid(timestamp, price);
            map.put(timestamp, bid);
            maxHeap.offer(bid);
            minHeap.offer(bid);
        }

        public int current() {
            return cur;
        }

        public int maximum() {
            //将堆顶失效价格移除
            while (!maxHeap.peek().enable) {
                maxHeap.poll();
            }
            return maxHeap.peek().price;
        }

        public int minimum() {
            //将堆顶失效价格移除
            while (!minHeap.peek().enable) {
                minHeap.poll();
            }
            return minHeap.peek().price;
        }
    }

    //p2335
    public int fillCups(int[] amount) {
        PriorityQueue<Integer> bigRootHeap = new PriorityQueue<>(Comparator.reverseOrder());
        for (int i = 0; i < 3; ++i) {
            if (amount[i] > 0) {
                bigRootHeap.offer(amount[i]);
            }
        }
        int answer = 0;
        while (!bigRootHeap.isEmpty()) {
            int a = bigRootHeap.poll();
            --a;
            int b = -1;
            if (!bigRootHeap.isEmpty()) {
                b = bigRootHeap.poll();
            }
            if (b > 0) {
                --b;
            }
            if (a > 0) {
                bigRootHeap.offer(a);
            }
            if (b > 0) {
                bigRootHeap.offer(b);
            }
            ++answer;
        }
        return answer;
    }

    /**
     * 2336【优先队列+哈希表】无限集中的最小数字
     */
    static class SmallestInfiniteSet {
        //记录已经addBack的数据，保证重复的addBack不会产生重复的元素
        private boolean[] added;
        //记录已经addBack的数据，保证元素最小的在堆顶，快速取最小元素
        private PriorityQueue<Integer> pq;
        //记录已经取出前面最小的数字之后当前无限集中未取出的最小元素
        private int n;
        public SmallestInfiniteSet() {
            added = new boolean[1001];
            pq = new PriorityQueue<>(Comparator.naturalOrder());
            n = 1;
        }

        public int popSmallest() {
            if (!pq.isEmpty() && pq.peek() < n) {
                //堆不空且堆里面的addBack元素更小，返回addBack的最小元素
                added[pq.peek()] = false;
                return pq.poll();
            }
            //否则是n更小，返回n
            int ret = n;
            ++n;
            return ret;
        }

        public void addBack(int num) {
            //如果addBack的值是已经addBack过的或集合中从未弹出的值，忽略
            if (added[num] || num >= n) return;
            added[num] = true;
            pq.offer(num);
        }
    }

    //p2357
    public int minimumOperations(int[] nums) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.naturalOrder());
        for (int num : nums) {
            if (num > 0) {
                heap.offer(num);
            }
        }
        int op = 0;
        while (!heap.isEmpty()) {
            int min = heap.poll();
            PriorityQueue<Integer> heap2 = new PriorityQueue<>(Comparator.naturalOrder());
            while (!heap.isEmpty()) {
                int rest = heap.poll() - min;
                if (rest > 0) {
                    heap2.offer(rest);
                }
            }
            heap = heap2;
            ++op;
        }
        return op;
    }

    /**
     * 2454【小根堆】下一个更大元素 IV
     */
    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        PriorityQueue<int[]> firstGreaterWait = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        PriorityQueue<int[]> secondGreaterWait = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        firstGreaterWait.offer(new int[]{0, nums[0]});
        for (int i = 1; i < n; ++i) {
            int num = nums[i];
            while (!secondGreaterWait.isEmpty() && secondGreaterWait.peek()[1] < num) {
                //num也大于待寻找第二大整数的元素，则这个元素的第二大整数就是num
                answer[secondGreaterWait.poll()[0]] = num;
            }
            while (!firstGreaterWait.isEmpty() && firstGreaterWait.peek()[1] < num) {
                //num也大于待寻找第一大整数的元素，如果num是某个元素的第一大元素，则此元素移到待寻找第二大的元素队列中
                secondGreaterWait.offer(firstGreaterWait.poll());
            }
            //num自己也进入待寻找第一大整数的元素队列
            firstGreaterWait.offer(new int[]{i, num});
        }
        return answer;
    }

    /**
     * 2931【优先堆】购买物品的最大开销
     */
    public long maxSpending(int[][] values) {
        long answer = 0;
        int m = values.length, n = values[0].length;
        int day = 1, end = m * n;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> values[a[0]][a[1]]));
        for (int i = 0; i < m; ++i) {
            pq.offer(new int[]{i, n - 1});
        }
        while (day <= end) {
            int[] a = pq.poll();
            answer += (long) day * values[a[0]][a[1]];
            if (a[1] > 0) {
                pq.offer(new int[]{a[0], a[1] - 1});
            }
            ++day;
        }
        return answer;
    }

    public static void main(String[] args) {
        PriorityQueueSolution solution = new PriorityQueueSolution();
        Assert.isTrue(7 == solution.eatenApples(new int[]{1,2,3,5,2}, new int[]{3,2,1,4,2}));
//        Assert.isTrue(2 == solution.minimumEffortPath(Parser.parse("[[1,2,2],[3,8,2],[5,3,5]]")));
    }
}
